Grokking Microsoft Coding Interview
Rate this course
Ask Author
Contribute
Back to course home

0% completed

Vote For New Content
Introduction
Who Should Take This Course?
Microsoft Easy Problems
Buddy Strings (easy)
Solution: Buddy Strings
Can Place Flowers (easy)
Solution: Can Place Flowers
Reverse a LinkedList (easy)
Solution: Reverse a LinkedList
Maximum Number of Balloons (easy)
Solution: Maximum Number of Balloons
Binary Tree Path Sum (easy)
Solution: Binary Tree Path Sum
Pair with Target Sum (easy)
Solution: Pair with Target Sum
Buy Two Chocolates (easy)
Solution: Buy Two Chocolates
Root Equals Sum of Children (easy)
Solution: Root Equals Sum of Children
Excel Sheet Column Title (easy)
Solution: Excel Sheet Column Title
Merge Strings Alternately (easy)
Solution: Merge Strings Alternately
Min Cost Climbing Stairs (easy)
Solution: Min Cost Climbing Stairs
Plus One (easy)
Solution: Plus One
Intersection of Two Arrays (easy)
Solution: Intersection of Two Arrays
Find the Index of the First Occurrence in a String (easy)
Solution: Find the Index of the First Occurrence in a String
Merge Two Sorted Lists (easy)
Solution: Merge Two Sorted Lists
Microsoft Medium Problems
Nth Digit (medium)
Solution: Nth Digit
Restore IP Addresses (medium)
Solution: Restore IP Addresses
Find Original Array From Doubled Array (medium)
Solution: Find Original Array From Doubled Array
Reverse Words in a String II (medium)
Solution: Reverse Words in a String II
Longest Arithmetic Subsequence (medium)
Solution: Longest Arithmetic Subsequence
Matchsticks to Square (medium)
Solution: Matchsticks to Square
Score of Parentheses (medium)
Solution: Score of Parentheses
Maximum Length of a Concatenated String with Unique Characters (medium)
Solution: Maximum Length of a Concatenated String with Unique Characters
Inorder Successor in BST (medium)
Solution: Inorder Successor in BST
Distribute Coins in Binary Tree (medium)
Solution: Distribute Coins in Binary Tree
Spiral Matrix (medium)
Solution: Spiral Matrix
Delete Node in a BST (medium)
Solution: Delete Node in a BST
Sum of Subarray Minimums (medium)
Solution: Sum of Subarray Minimums
Rotate Image (medium)
Solution: Rotate Image
Combinations (medium)
Solution: Combinations
Maximum Level Sum of a Binary Tree (medium)
Solution: Maximum Level Sum of a Binary Tree
Multiply Strings (medium)
Solution: Multiply Strings
Best Time to Buy and Sell Stock II (medium)
Solution: Best Time to Buy and Sell Stock II
Largest Palindromic Number (medium)
Solution: Largest Palindromic Number
Remove Duplicate Letters (medium)
Solution: Remove Duplicate Letters
Next Permutation (medium)
Solution: Next Permutation
132 Pattern (medium)
Solution: 132 Pattern
Valid Sudoku (medium)
Solution: Valid Sudoku
Number of Islands (medium)
Solution: Number of Islands
Buildings With an Ocean View (medium)
Solution: Buildings With an Ocean View
Regular Expression Matching (hard)
Solution: Regular Expression Matching
First Missing Positive (hard)
Solution: First Missing Positive
Largest Rectangle in Histogram (hard)
Solution: Largest Rectangle in Histogram
Sliding Window Maximum (hard)
Solution: Sliding Window Maximum
Count Unique Characters of All Substrings of a Given String (hard)
Solution: Count Unique Characters of All Substrings of a Given String
Word Ladder (hard)
Solution: Word Ladder
Word Ladder II (hard)
Solution: Word Ladder II
Number of Flowers in Full Bloom (hard)
Solution: Number of Flowers in Full Bloom
Median of Two Sorted Arrays (hard)
Solution: Median of Two Sorted Arrays
Longest Valid Parentheses (hard)
Solution: Longest Valid Parentheses
Solution: Reverse Words in a String II

Problem Statement

Given a character array s, return the updated array after reversing the order of words in the array.

A word is defined as a sequence of non-space characters, and the words are separated by one space character. The input array does not contain any leading or trailing spaces, and the words are always separated by a single space.

Note: Your code must solve the problem without using any extra space.

Examples

  • Example 1:

    • Input: ["h","e","l","l","o"," ","w","o","r","l","d"]
    • Expected Output: ["w","o","r","l","d"," ","h","e","l","l","o"]
    • Justification: The original string is "hello world". Reversing the words gives "world hello".
  • Example 2:

    • Input: ["m","o","r","n","i","n","g"," ","s","k","y"," ","i","s"," ","b","r","i","g","h","t"]
    • Expected Output: ["b","r","i","g","h","t"," ","i","s"," ","s","k","y"," ","m","o","r","n","i","n","g"]
    • Justification: The original string is "morning sky is bright". Reversing the words gives "bright is sky morning".
  • Example 3:

    • Input: ["a","l","o","n","e"]
    • Expected Output: ["a","l","o","n","e"]
    • Justification: There's only one word "alone", so the reverse is the same as the original.

Solution

To solve this problem, the approach involves two main steps: first, reverse the entire array to get the words in the reverse order but with the characters of each word also reversed. Second, reverse the characters of each word to correct their orientation. This method works because reversing the entire array places the words in their final positions relative to each other, and then reversing the characters within each word ensures that the words are oriented correctly. This approach is effective because it allows us to achieve the desired result with a simple, two-pass solution that operates directly on the array in-place, ensuring that no additional space is required beyond minimal temporary variables.

This method is chosen for its efficiency and simplicity. By manipulating the array in place, we avoid the overhead of extra memory allocation that would be required for a solution that constructs a new array or uses additional data structures. This makes the algorithm particularly suitable for large inputs and constraints where space efficiency is a concern.

Step-by-Step Algorithm

  1. Reverse the entire array of characters.

    • Identify the start and end indexes of the array.
    • Swap characters at the start and end indexes.
    • Increment the start index and decrement the end index.
    • Continue this process until the start index is greater than or equal to the end index.
  2. Identify the bounds of each word.

    • Initialize a variable to track the start of the current word.
    • Iterate through the array with an index variable.
      • If a space character or the end of the array is encountered, the current index marks the end of a word.
  3. Reverse each word identified in step 2.

    • For each word, repeat the reversal process used in step 1, but apply it only to the characters within the bounds of the word.
      • Swap characters at the start and end of the word.
      • Increment the word's start index and decrement the word's end index.
      • Continue this process until the start index of the word is greater than or equal to the end index of the word.

Algorithm Walkthrough

Consider the input: ["m","o","r","n","i","n","g"," ","s","k","y"," ","i","s"," ","b","r","i","g","h","t"]

  1. Reverse the entire array:

    • Initial array: ["m", "o", "r", "n", "i", "n", "g", " ", "s", "k", "y", " ", "i", "s", " ", "b", "r", "i", "g", "h", "t"]
    • After reversing: ["t", "h", "g", "i", "r", "b", " ", "s", "i", " ", "y", "k", "s", " ", "g", "n", "i", "n", "r", "o", "m"]
  2. Identify bounds of each word and reverse:

    • Word 1 ("t", "h", "g", "i", "r", "b"): Reverse to get ["b", "r", "i", "g", "h", "t"].
    • Word 2 ("s", "i"): Reverse to get ["i", "s"].
    • Word 3 ("y", "k", "s"): Reverse to get ["s", "k", "y"].
    • Word 4 ("g", "n", "i", "n", "r", "o", "m"): Reverse to get ["m", "o", "r", "n", "i", "n", "g"].
  3. Final array:

    • ["b", "r", "i", "g", "h", "t", " ", "i", "s", " ", "s", "k", "y", " ", "m", "o", "r", "n", "i", "n", "g"]

Code

Java
Saved to Cloud

. . . .

Complexity Analysis

  • Time Complexity: The overall time complexity of the algorithm is , where n is the length of the input array. This is because each character is visited twice at most - once during the entire array reversal and once during the reversal of each word.

  • Space Complexity: The space complexity is , as the reversal is done in place, and no additional space proportional to the input size is used.

Reverse Words in a String II (medium)
Longest Arithmetic Subsequence (medium)
Mark as Completed

On this page

Problem Statement

Examples

Solution

Step-by-Step Algorithm

Algorithm Walkthrough

Code

Complexity Analysis